#include "main.h"
#include <cstdlib>

struct PathNode
{
	Node* dataNode;

	PathNode* next;
	PathNode* prev;

	PathNode(Node* node): dataNode(node), next(NULL), prev(NULL) {}
	~PathNode()
	{
		if (next)
		{
			delete next;
		}
	}
};

Node*		g_head = new Node;
PathNode*	g_searchPath;

void searchPathPush(Node* node)
{
	PathNode* n = new PathNode(node);

	if (g_searchPath == NULL)
	{
		g_searchPath = n;
		return;
	}

	n->next = g_searchPath;
	g_searchPath->prev = n;
	g_searchPath = n;
}

Node* searchPathPop()
{
	if (g_searchPath == NULL)
	{
		return NULL;
	}

	Node* node = g_searchPath->dataNode;
	PathNode* n = g_searchPath;
	g_searchPath = g_searchPath->next;
	n->next = NULL;
	delete n;

	return node;
}

int search(int key)
{
	// clean search path
	if (g_searchPath)
	{
		delete g_searchPath;
		g_searchPath = NULL;
	}

	Node* p = g_head;

	while (p->down || p->key != key)
	{
		bool goDown = false;

		if (p->key <= key)
		{
			if (p->next)
			{
				p = p->next;
			}
			else
			{
				goDown = true;
			}
		}
		else
		{
			p = p->prev;
			goDown = true;
		}

		if (goDown)
		{
			searchPathPush(p);

			if (p->down)
			{
				p = p->down;
			}
			else
			{
				return NEGTIVE_INFINITE;
			}
		}
	}

	searchPathPush(p);
	return p->data;
}

void insert(int key, int data)
{
	search(key);

	Node* downNode = NULL;

	bool shouldContinue;

	do
	{
		Node* prevNode;

		if (g_searchPath)
		{
			prevNode = searchPathPop();
		}
		else
		{
			prevNode = g_head;
		}

		Node* node = new Node;
		node->key = key;
		node->data = data;

		node->next = prevNode->next;
		node->prev = prevNode;

		if (prevNode->next)
		{
			prevNode->next->prev = node;
		}

		prevNode->next = node;

		if (downNode)
		{
			downNode->up = node;
			node->down = downNode;
		}

		downNode = node;

		int r = rand();
		shouldContinue = (r < (RAND_MAX >> 1));

		if (shouldContinue && (g_searchPath == NULL))
		{
			Node* newHead = new Node;
			newHead->down = g_head;
			g_head->up = newHead;
			g_head = newHead;
		}
	}
	while (shouldContinue);
}

void remove(int key)
{

}
